#
# @lc app=leetcode.cn id=53 lang=python
#
# [53] 最大子序和
#

# @lc code=start
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 动态规划，O(n)
        for i in range(1, len(nums)):
            nums[i] = nums[i] + max(nums[i-1], 0)
        print(nums)
        return max(nums)


class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 贪心算法
        res = nums[0]
        sum = 0
        for num in nums:
            if sum > 0:
                sum += num
            else:
                sum = num
            res = max(res, sum)

        return res

# @lc code=end


if __name__ == "__main__":
    solution = Solution()
    max_num = solution.maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])
    print(max_num)